#ifndef OCT_TREE_H
#define OCT_TREE_H

#include "stdafx.h"
#include <vector>
#include "Maths.h"

#define OCT_TREE_BUCKET_SIZE 10;


template <typename T>
class OctNode
{
private:
	void SplitNode()
	{
		if(this->isSplit == false)
		{
			this->isSplit = true;
			hasChildren = false;
			//split node 
			Vec3<T> minPoint = this->limits->GetMinPoint();
			Vec3<T> maxPoint = this->limits->GetMaxPoint();;
			Vec3<T> minLimit;
			Vec3<T> maxLimit;

			Vec3<T> middlePoint((maxPoint.x + minPoint.x)/2, (maxPoint.y + minPoint.y)/2, (maxPoint.z + minPoint.z) / 2);

			cout<< "Splitting current node"<< endl;

			BoundingBox<T> *lowerBoundingBox1 = new BoundingBox<T>(minPoint, middlePoint);
			this->childrenNodes[0] = new OctNode<T>(lowerBoundingBox1);

			BoundingBox<T> *lowerBoundingBox2 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, minPoint.z), Vec3<T>(maxPoint.x, middlePoint.y, middlePoint.z));
			this->childrenNodes[1] = new OctNode<T>(lowerBoundingBox2);

			BoundingBox<T> *lowerBoundingBox3 = new BoundingBox<T>(Vec3<T>(minPoint.x, minPoint.y, middlePoint.z), Vec3<T>(middlePoint.x, middlePoint.y, maxPoint.z));
			this->childrenNodes[2] = new OctNode<T>(lowerBoundingBox3);

			BoundingBox<T> *lowerBoundingBox4 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, middlePoint.z), Vec3<T>(maxPoint.x, middlePoint.y, maxPoint.z));
			this->childrenNodes[3] = new OctNode<T>(lowerBoundingBox4);

			//continue from here 
			BoundingBox<T> *lowerBoundingBox5 = new BoundingBox<T>(Vec3<T>(minPoint.x, middlePoint.y, minPoint.z), Vec3<T>(middlePoint.x, maxPoint.y, middlePoint.z));
			this->childrenNodes[4] = new OctNode<T>(lowerBoundingBox5);

			BoundingBox<T> *lowerBoundingBox6 = new BoundingBox<T>(Vec3<T>(middlePoint.x, middlePoint.y, minPoint.z), Vec3<T>(maxPoint.x, maxPoint.y, middlePoint.z));
			this->childrenNodes[5] = new OctNode<T>(lowerBoundingBox6);

			BoundingBox<T> *lowerBoundingBox7 = new BoundingBox<T>(Vec3<T>(minPoint.x, middlePoint.y, middlePoint.z), Vec3<T>(middlePoint.x, maxPoint.y, maxPoint.z));
			this->childrenNodes[6] = new OctNode<T>(lowerBoundingBox7);

			BoundingBox<T> *lowerBoundingBox8 = new BoundingBox<T>(middlePoint, maxPoint);
			this->childrenNodes[7] = new OctNode<T>(lowerBoundingBox8);
		}
	}

public:

	bool hasChildren;
	bool isSplit;
	OctNode<T> *childrenNodes[8];
	vector<Vec3<T>> containedPoints;
	BoundingBox<T> *limits;

	OctNode(BoundingBox<T> *limitsBox)
	{
		this->limits = limitsBox;
		hasChildren = false;
		isSplit = false;
	}

	OctNode()
	{
		hasChildren = false;
		isSplit = false;
	}

	~OctNode()
	{
		delete limits;
	}

	void InsertPoint(Vec3<T> currentPoint)
	{
	bool alreadyContained = false;
		for(int index = 0; index < containedPoints.size(); index++)
		{
			
			Vec3<T> containedPoint = containedPoints[index];

			if(currentPoint == containedPoint)
			{
				alreadyContained = true;
				break;
			}
		}

		if(!alreadyContained)
		{
			containedPoints.push_back(currentPoint);
			hasChildren = true;
			cout << "inserting point"<< endl;
			//if bucket contains more points than the bucket size limit split the oct tree
			if(containedPoints.size() > 5)
			{
				hasChildren = false;
				SplitNode();

				//foreach child in the following bucket
				for(int pointIndex  = 0; pointIndex < this->containedPoints.size(); pointIndex ++)
				{
					Vec3<T> currentPoint = this->containedPoints[pointIndex];
					bool flag = false;
					for(int octIndex = 0; octIndex < 8; octIndex ++)
					{
						OctNode<T> *currentChildNode = this->childrenNodes[octIndex];
						if(currentChildNode->limits->CheckIfPointContained(currentPoint))
						{
							currentChildNode->InsertPoint(currentPoint);
							flag = true;
							break;
						}
					}

					if(!flag)
					{
						cout<< "no node found" << endl;
					}
				}

				this->containedPoints.empty();
			}
		}
	}

	void static SplitNode(Vec3<T> maxPoint, Vec3<T> minPoint)
	{
		//if(this->isSplit == false)
		//{
		////	this->isSplit = true;
		//	hasChildren = false;
			//split node 
			Vec3<T> minLimit;
			Vec3<T> maxLimit;

			Vec3<T> middlePoint((maxPoint.x + minPoint.x)/2, (maxPoint.y + minPoint.y)/2, (maxPoint.z + minPoint.z) / 2);

			cout<< "Splitting current node"<< endl;

			BoundingBox<T> *lowerBoundingBox1 = new BoundingBox<T>(minPoint, middlePoint);
			//this->childrenNodes[0] = new OctNode<T>(lowerBoundingBox1);

			BoundingBox<T> *lowerBoundingBox2 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, minPoint.z), Vec3<T>(maxPoint.x, middlePoint.y, middlePoint.z));
			//this->childrenNodes[1] = new OctNode<T>(lowerBoundingBox2);

			BoundingBox<T> *lowerBoundingBox3 = new BoundingBox<T>(Vec3<T>(minPoint.x, minPoint.y, middlePoint.z), Vec3<T>(middlePoint.x, middlePoint.y, maxPoint.z));
			//this->childrenNodes[2] = new OctNode<T>(lowerBoundingBox3);

			BoundingBox<T> *lowerBoundingBox4 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, middlePoint.z), Vec3<T>(maxPoint.x, middlePoint.y, maxPoint.z));
			//this->childrenNodes[3] = new OctNode<T>(lowerBoundingBox4);

			//continue from here 
			BoundingBox<T> *lowerBoundingBox5 = new BoundingBox<T>(Vec3<T>(minPoint.x, middlePoint.y, minPoint.z), Vec3<T>(middlePoint.x, maxPoint.y, middlePoint.z));
			//this->childrenNodes[4] = new OctNode<T>(lowerBoundingBox5);

			BoundingBox<T> *lowerBoundingBox6 = new BoundingBox<T>(Vec3<T>(middlePoint.x, middlePoint.y, minPoint.z), Vec3<T>(maxPoint.x, maxPoint.y, middlePoint.z));
			//this->childrenNodes[5] = new OctNode<T>(lowerBoundingBox6);

			BoundingBox<T> *lowerBoundingBox7 = new BoundingBox<T>(Vec3<T>(minPoint.x, middlePoint.y, middlePoint.z), Vec3<T>(middlePoint.x, maxPoint.y, maxPoint.z));
			//this->childrenNodes[6] = new OctNode<T>(lowerBoundingBox7);

			BoundingBox<T> *lowerBoundingBox8 = new BoundingBox<T>(middlePoint, maxPoint);
			//this->childrenNodes[7] = new OctNode<T>(lowerBoundingBox8);
		//}
	}
};
  
template <typename T>
class OctTree
{
private:
	OctNode<T> *rootNode;
	bool CheckIfContained(OctNode<T> *currentNode, Vec3<T> testPoint)
	{
		if(currentNode->isSplit)
		{
			//check which node should it travers to
			for(int nodeIndex = 0; nodeIndex < 8; nodeIndex++)
			{
				OctNode<T> *currentChildNode = currentNode->childrenNodes[nodeIndex];

				if(currentChildNode->limits->CheckIfPointContained(testPoint))
				{
					return CheckIfContained(currentChildNode, testPoint);
				}
			}
		}
		else if(currentNode->hasChildren)
		{
			for(int pointsIndex = 0; pointsIndex < currentNode->containedPoints.size(); pointsIndex++)
			{
				if(currentNode->containedPoints[pointsIndex] == testPoint)
				{
					return true;
				}
			}

			return false;
		}
	}

public:

	OctTree(vector<Vec3<T>> listOfPoints)
	{
		T minX = INT_MAX, maxX = INT_MIN, minY = INT_MAX, maxY = INT_MIN, maxZ = INT_MIN, minZ = INT_MAX;

		for(int pointIndex = 0; pointIndex < listOfPoints.size(); pointIndex++)
		{
			Vec3<T> currentPoint = listOfPoints[pointIndex];

			minX = min(currentPoint.x, minX);
			maxX = max(currentPoint.x , maxX);

			minY = min(currentPoint.y , minY);
			maxY = max(currentPoint.y, maxY);

			minZ = min(currentPoint.z, minZ);
			maxZ = max(currentPoint.z, maxZ);
		}

		Vec3<T> minPoint(minX, minY, minZ);
		Vec3<T> maxPoint(maxX, maxY, maxZ);

		BoundingBox<T> *rootBoundingBox = new BoundingBox<T>(minPoint, maxPoint);
		
		this->rootNode = new OctNode<T>(rootBoundingBox);
		CreateOctTree(listOfPoints);
	}

	void CreateOctTree(vector<Vec3<T>> pointList)
	{
		for(int pointIndex = 0; pointIndex < pointList.size(); pointIndex ++)
		{
			this->rootNode->InsertPoint(pointList[pointIndex]);
			cout << pointIndex << endl;
		}
	}

	bool CheckIfContained(Vec3<T> currentPoint)
	{
		return this->CheckIfContained(this->rootNode, currentPoint);
	}
};


/*
#ifndef OCT_TREE_H
#define OCT_TREE_H


#include "stdafx.h"
#include "Maths.h"
#include <vector>

using namespace std;
#define BUCKET_SIZE_LIMIT 10;

template <typename T>
class OctNode
{


public:
	bool isChild = false;
	BoundingBox<T> *limits;
	vector<Vec3<T>> childPoints;
	OctNode<T> *childrenNodes[8];
	bool hasChildNodes = false;

	OctNode(BoundingBox<T> *limitsBox)
	{
		isChild = false;
		this->limits = limitsBox;
	}

	void CheckIfContains(Vec3<T> currentPoint)
	{
		if(limits->CheckIfBoxContainsPoint(currentPoint))
		{
			this->InsertPoint(currentPoint);
			return true;
		}
		return false;
	}

	void InsertPoint(Vec3<T> currentPoint)
	{
		childPoints.push_back(currentPoint);
		if(childPoints.size() < BUCKET_SIZE_LIMIT )
		{
			isChild = true;
		}
		else
		{
			SplitNode();

			for(int childrenIndex = 0; childrenIndex < childPoints.size(); childrenIndex++)
			{
				for(int childrenNodes = 0; childrenNodes < 8; childrenNodes ++)
				{
					OctNode<T> *currentOctNode = childrenNodes[childrenNodes];

					if(currentOctNode->CheckIfContains(childPoints[childrenIndex]))
					{
						currentOctNode->InsertPoint(childPoints[childrenIndex]);
					}
				}
			}
		}
	}

	private :
	void SplitNode()
	{
		if(!this->hasChildNodes)
		{
			isChild = false;
			//do the other stuff
			//get the limits and produce the new 8 bounding boxes
			Vec3<T> maxPoint = this->limits->maxPoint;
			Vec3<T> minPoint = this->limits->minPoint;
			Vec3<T> middlePoint = (maxPoint + minPoint)/ 2;

			BoundingBox<T> *lowerBoundingBox1 = new BoundingBox<T>(minPoint, middlePoint);
			this->childrenNodes[0] = new OctNode<T>(lowerBoundingBox1);

			BoundingBox<T> *lowerBoundingBox2 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, minPoint.z), Vec3<T>(maxPoint.x, maxPoint.y, middlePoint.z));
			this->childrenNodes[1] = new OctNode<T>(lowerBoundingBox2);

			BoundingBox<T> *lowerBoundingBox3 = new BoundingBox<T>(Vec3<T>(minPoint.x, minPoint.y, middlePoint.z), Vec3<T>(middlePoint.x, middlePoint.y, maxPoint.z));
			this->childrenNodes[2] = new OctNode<T>(lowerBoundingBox3);

			BoundingBox<T> *lowerBoundingBox4 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, middlePoint.z), Vec3<T>(middlePoint.x, middlePoint.y, maxPoint.z));
			this->childrenNodes[3] = new OctNode<T>(lowerBoundingBox4);

			//continue from here 
			BoundingBox<T> *lowerBoundingBox5 = new BoundingBox<T>(Vec3<T>(middlePoint.x, minPoint.y, minPoint.z), Vec3<T>(middlePoint.x, maxPoint.y, middlePoint.z));
			this->childrenNodes[4] = new OctNode<T>(lowerBoundingBox5);

			BoundingBox<T> *lowerBoundingBox6 = new BoundingBox<T>(Vec3<T>(middlePoint.x, middlePoint.y, minPoint.z), Vec3<T>(middlePoint.x, maxPoint.y, middlePoint.z));
			this->childrenNodes[5] = new OctNode<T>(lowerBoundingBox6);

			BoundingBox<T> *lowerBoundingBox7 = new BoundingBox<T>(Vec3<T>(minPoint.x, middlePoint.y, middlePoint.z), Vec3<T>(middlePoint.x, maxPoint.y, maxPoint.z));
			this->childrenNodes[6] = new OctNode<T>(lowerBoundingBox7);

			BoundingBox<T> *lowerBoundingBox8 = new BoundingBox<T>(middlePoint, maxPoint);
			this->childrenNodes[7] = new OctNode<T>(lowerBoundingBox8);
		} 
	}

	
};

template <typename T>
class OctTree
{
private:
	OctNode<T> *rootNode;

	OctTree(vector<Vec3<T>> allPoints)
	{
		rootNode = new OctNode<T>();
	}

	void BuildOctree(vector<Vec3<T>> allPoints)
	{
		for(int x = 0; x < allPoints.size(); x ++)
		{
			rootNode->InsertPoint(allPoints[x]);
		}
	}
};

#endif 
*/

#endif